package com.zhn;

//给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

import java.util.*;

public class LevelOrderBottom {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        travel(root);
        return result;
    }

    private void travel(TreeNode node) {
        if(node == null)
            return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        //offer       添加一个元素并返回true       如果队列已满，则返回false
        que.add(node);
        while(!que.isEmpty()){
            List<Integer> res = new ArrayList<>();
            int len = que.size();

            while(len-->0){
                TreeNode tmpNode = que.poll();
                res.add(tmpNode.val);
                if (tmpNode.left != null)que.add(tmpNode.left);
                if(tmpNode.right != null)que.add(tmpNode.right);
            }
            //ArrayList的重载方法
            /**
             * 在此列表中的指定位置插入指定的元素。将当前位于该位置的元素（如果有）和任何后续元素向右移动（在其索引中添加一个）。
             * 参数：
             * index – 要插入指定元素的索引 element – 要插入的元素
             * 抛出：
             * IndexOutOfBoundsException – 如果索引超出范围 （index < 0 || index > size()）
             */
            //头插法插入元素，将每层结果从头位置放入，其他的后移，反转结果
            result.add(0,res);
        }
    }
}
